import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class RightVeiw {
    public List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    // first time add root
    while (!queue.isEmpty()) {
        // first time size = 1
        // 第二次 size = 2(2,3)
        int size = queue.size();
        //[利用队列先进先出的特性
        result.add(queue.peek().val);
        for (int i = 0; i < size; i++) {
            //第二次poll 3
            // 第二次的循环 2 poll 2
            TreeNode node = queue.poll();
            //queue -> 	4 -> 2
            // queue -> 5 -> 4
            if (node.right != null) {
                queue.add(node.right);
            }
            //
            if (node.left != null) {
                queue.add(node.left);
            }
        }
        // after first loop, queue -> 2 -> 3
        // 第二次循环之后5 -> 4
    }
    return result;
}


}
